package com.fyl.basic_algorithm.backtrack;

/**
 * @Description: 八皇后问题
 * @author:fyl
 * @date 2021/4/7 11:14
 * @Modified By:
 * @Modified Date:
 */
public class Queens {
    int[] result = new int[8]; //下标表示行，值表示储存在那一列

    //调用方式cal8queens(0)
    public void cal8queens(int row) {
        if (row == 8) { //8个棋子都放置完成
            printQueens(result);
            return;
        }

        for (int column = 0; column < 8; column++) {
            if (isOk(row, column)) {//判断放法是否满足要求
                result[row] = column;  //第i行放到第column列
                cal8queens(row + 1); //考察下一行
            }
        }
    }

    /**
     * 判断row行column列放置是否合适
     *
     * @param row    行
     * @param column 列
     */
    private boolean isOk(int row, int column) {
        int leftUp = column - 1;
        int rightUp = column + 1;
        for (int i = row - 1; i >= 0; --i) {  //逐行往上考察每一行
            if (result[i] == column) return false;  //第i行的column列是否有棋子
            if (leftUp >= 0) {  //检查左上对角线,第i行第leftUp列是否有棋子
                if (result[i] == leftUp) return false;
            }
            if (rightUp < 8) {  //检查右上角对角线，第i行第rightUp列是否有棋子
                if (result[i] == rightUp) return false;
            }
            --leftUp;
            ++rightUp;
        }
        return true;
    }

    private void printQueens(int[] result) {
        for (int row = 0; row < 8; row++) {
            for (int column = 0; column < 8; column++) {
                if (result[row] == column)
                    System.out.print("Q ");
                else
                    System.out.print("* ");
            }
            System.out.println();
        }
        System.out.println();
    }


}

class Test {
    public static void main(String[] args) {
        Queens queens = new Queens();
        queens.cal8queens(0);
    }
}
